문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 불완전성 정리 (문단 편집) === 주요 개념 === [[수리논리학]]에서 쓰이는 "[[참]]", "증명가능성", "귀결" 등의 개념은 자칫 오해하기 쉽다. 오해를 방지하기 위하여 관련 개념을 약술하자면 다음과 같다: "불완전성 정리"에서 말하는 '''"완전성(completeness)"'''이란 '''"건전성(soundness)"'''과 대비되는 성질이다.[* 비슷한 맥락에서 중요한 성질로 [[콤팩트성]] 정리가 있다. 이는 위상수학의 compact 개념을 적용한 것으로, "[math(\phi)]가 명제들의 집합 [math(\Gamma)]의 귀결이면, [math(\Gamma)]의 유한한 부분집합 [math(\Gamma')]이 존재해서 [math(\phi)]가 [math(\Gamma')]의 귀결이다"가 성립한다는 것이다.] 임의의 형식 체계 [math(P)], 명제 집합 [math(\Gamma)], 그리고 명제 [math(\phi)]에 관하여 이들 개념은 다음과 같이 정의될 수 있다: > * [math(P)]의 '''건전성''': [math(P)]에서 [math(\Gamma)]로부터 [math(\phi)]가 증명가능하다면, [math(P)]에서 [math(\phi)]는 [math(\Gamma)]의 논리적 귀결이다. > * [math(P)]가 건전하면 [math(P)]는 무모순적이다. > * [math(P)]의 '''완전성''': [math(P)]에서 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이라면, [math(\phi)]가 [math(P)]에서 타당하다면, [math(P)]에서 명제 [math(\phi)]는 [math(\Gamma)]로부터 증명가능하다. 이때 "증명가능성"과 "논리적 귀결"은 각각 다음과 같이 정의된다: > * [math(P)]에서 [math(\phi)]는 [math(\Gamma)]로부터 '''증명가능하다''' [math(\Leftrightarrow)] [math(\Gamma)]의 원소들 및 [math(P)]의 [[공리]]들에 [math(P)]의 도출 규칙을 유한번 적용하여 [math(\phi)]를 얻을 수 있다. > * [math(P)]에서 [math(\phi)]는 [math(\Gamma)]의 '''논리적 귀결이다''' [math(\Leftrightarrow)] [math(P)]에서 [math(\Gamma)]의 모든 원소들이 참인 경우 [math(\phi)]도 반드시 참이다 [math(\Leftrightarrow)] [math(\Gamma)]의 모든 원소들이 참인 임의의 모형에서 [math(\phi)]는 참이다. [[명제 논리]]는 건전하며 완전하다. 더욱이 명제 논리의 경우 임의의 [math(\Gamma)]와 [math(\phi)]에 대하여 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결인지 여부를 유한번 단계 내에 판단할 수 있게끔 해주는 절차가 있으므로 결정가능하다. [[양화 논리|1차 술어 논리]]는 건전한 동시에 완전하지만, 결정가능하지는 않다. 따라서 만약 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이라면 그 사실은 유한 번 단계 내에 판단할 수 있지만, [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이 아니라면 그럴 수 없다. 1차 술어 논리의 완전성 또한 괴델이 증명한 것이다. 자연수 산술을 가능케 하는 [[페아노 공리계]]를 포함하는 형식 체계는 1차 논리보다 강력하다. 괴델의 불완전성 정리는 이런 논리 체계가 '''완전성'''을 띠지 않는다는 점을 보여주는 것이다. 곧 설령 참이라 한들 그에 대한 증명도, 그 부정에 대한 증명도 불가능한 문장들이 있다는 것이다. 밑에서도 나오겠지만 [[연속체 가설]]을 비롯한 몇몇 [[명제]]들이 바로 그 사례다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기